// POJ3311 Hie with the Pie
// 陈锋
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int NN = 10 + 1, INF = 0x3f3f3f3f;
int N, D[NN][NN], F[NN][1 << 12];  // 状态压缩

inline void floyd() {  // D(i,j)->i到j的最短距离
  for (int k = 0; k <= N; k++)
    for (int i = 0; i <= N; i++)
      for (int j = 0; j <= N; j++)
        D[i][j] = min(D[i][k] + D[k][j], D[i][j]);  // i-j的最短路
}
// F(i,s): 当前在i,还需要访问s中的点各一次
int dp(int i, int s) {
  int &f = F[i][s];
  if (s == 0) return f = D[i][0];  // 已达目的地
  if (f != -1) return f;
  f = INF;
  for (int j = 0; j <= N; j++) {
    if (s & (1 << j))  // j:下一个点
      f = min(f, D[i][j] + dp(j, s ^ (1 << j)));
  }
  return f;
}

int main() {
  while (scanf("%d", &N) == 1 && N) {
    memset(F, -1, sizeof(F)), memset(D, 0x3f, sizeof(D));
    for (int i = 0; i <= N; i++)
      for (int j = 0; j <= N; j++) scanf("%d", &D[i][j]);
    floyd();  // 结果dp(0, (1,2...N-1))
    printf("%d\n", dp(0, (1 << (N + 1)) - 2));
  }
}
/*
算法分析请参考: 《入门经典-第2版》 9.4.3一节 货郎担问题（TSP）
*/
// Accepted 500kB 985 G++2020-12-08 21:09:28 22197193